package org.leetcode.middle.leetcode491;

import java.util.*;

public class Solution {

    List<List<Integer>> res= new ArrayList<>();

    Stack<Integer> stack = new Stack<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }


    private void backtracking2(int [] nums,int startIndex){
        if (stack.size()>=2){
            res.add(new ArrayList<>(stack));
        }

        HashSet<Integer> used = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (stack.isEmpty() || stack.peek()<=nums[i]){

                if (used.contains(nums[i])){
                    continue;
                }

                used.add(nums[i]);
                stack.push(nums[i]);

                backtracking2(nums,i+1);
                //回溯中不需要在used删除当前元素，因为used就是用来统计当前元素
                stack.pop();
            }
        }
    }

    //错误，nums是无序的
    private void backtracking(int [] nums,int startIndex){

        if (stack.size()>=2){
            res.add(new ArrayList<>(stack));
        }

        for (int i = startIndex; i < nums.length ; i++) {
                if (stack.isEmpty()){
                    stack.push(nums[i]);
                }else if (stack.peek()<=nums[i]){

                    //去重
                    if (i>startIndex && nums[i]==nums[i-1]){
                        continue;
                    }
                    stack.push(nums[i]);

                    backtracking(nums,i+1);

                    stack.pop();
                }
        }
    }


}
